package leetcode.lcp03;

import leetcode.IDebug;

public class Solution implements IDebug {

	public int largestArea(String[] grid) {
		int m = grid.length, n = grid[0].length();
		UnionFindXY union = new UnionFindXY(m, n);
		union.init(grid);
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				union.union2(i, j);
			}
		}
		return union.ans();
	}

	class UnionFindXY {
		int[] roots;
		int[] sizes;
		int[] stack;
		int size;
		int m, n;
		//
		boolean[] isWay;
		boolean[] next;
		char[][] cs;

		public UnionFindXY(int m, int n) {
			size = m * n;
			this.m = m;
			this.n = n;
			roots = new int[size];
			sizes = new int[size];
			for (int i = 0; i < size; i++) {
				roots[i] = i;
				sizes[i] = 1;
			}
			stack = new int[size];
		}

		public void union2(int i, int j) {
			this.union(i - 1, j, i, j);
			this.union(i, j - 1, i, j);
		}

		public int ans() {
			int ans = 0;
			for (int i = 0; i < size; i++) {
				if (this.sizes[i] > 0 && !this.next[i]) {
					ans = Math.max(ans, this.sizes[i]);
				}
			}
			return ans;
		}

		public void init(String[] grid) {
			cs = new char[m][n];
			for (int i = 0; i < m; i++) {
				cs[i] = grid[i].toCharArray();
			}
			this.isWay = new boolean[size];
			this.next = new boolean[size];
			for (int i = 0; i < m; i++) {
				for (int j = 0; j < n; j++) {
					char c = cs[i][j];
					int index = this.index(i, j);
					if (c == '0') {
						this.isWay[index] = true;
						this.next[index] = true;
						this.sizes[index] = 0;
					} else {
						if (this.next(i, j, cs)) {
							this.next[index] = true;
						}
					}
				}
			}
		}

		int[] d = new int[] { 0, -1, 0, 1, -1, 0, 1, 0 };

		private boolean next(int x, int y, char[][] cs) {
			for (int i = 0; i < 8; i += 2) {
				int nextx = x + d[i], nexty = y + d[i + 1];
				if (nextx >= 0 && nextx < m && nexty >= 0 && nexty < n) {
					if (cs[nextx][nexty] == '0') {
						return true;
					}
				} else {
					return true;
				}
			}
			return false;
		}

		public int findRoot(int id) {
			int root = 0, p = 0;
			while ((root = roots[id]) != id) {
				stack[p++] = id;
				id = root;
			}
			while (p > 0) {
				roots[stack[--p]] = root;
			}
			return root;
		}

		public boolean isSameSet(int id1, int id2) {
			return findRoot(id1) == findRoot(id2);
		}

		public void union(int id1, int id2) {
			int p1 = this.findRoot(id1);
			int p2 = this.findRoot(id2);
			if (p1 != p2) {
				int size1 = this.sizes[p1];
				int size2 = this.sizes[p2];
				if (size1 < size2) {
					this.roots[p1] = p2;
					this.sizes[p2] = size1 + size2;
					this.sizes[p1] = 0;
					this.next[p2] = this.next[p1] || this.next[p2];
				} else {
					this.roots[p2] = p1;
					this.sizes[p1] = size1 + size2;
					this.sizes[p2] = 0;
					this.next[p1] = this.next[p1] || this.next[p2];
				}
			}
		}

		public boolean isSameSet(int x1, int y1, int x2, int y2) {
			int id1 = this.index(x1, y1);
			int id2 = this.index(x2, y2);
			return this.isSameSet(id1, id2);
		}

		public void union(int x1, int y1, int x2, int y2) {
			if (x1 < 0 || y1 < 0) {
				return;
			}
			int id1 = this.index(x1, y1);
			int id2 = this.index(x2, y2);
			if (cs[x1][y1] == cs[x2][y2] && cs[x1][y1] != '0') {
				this.union(id1, id2);
			}
			if (cs[x1][y1] == '0') {
				this.next[id2] = true;
				this.next[this.findRoot(id2)] = true;
			}
			if (cs[x2][y2] == '0') {
				this.next[id1] = true;
				this.next[this.findRoot(id1)] = true;
			}
		}

		public int index(int i, int j) {
			return i * n + j;
		}
	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
